package zuo.baseUP1_Hash;

/**
 * @Author: Forx
 * @Data: 2021/6/17
 * @Desc: Algorithm - zuo.baseUP1_Hash
 * @Version: v1.0
 */
public class Hash {
    /**
     * 设计 RandomPoo l结构
     * 题目】
     * 设计一种结构,在该结构中有如下三个功能
     * sert(key):将某个key加入到该结构,做到不重复加入
     * delete(key):将原本在结构中的某个key移除
     * getRandom():等概率随机返回结构中的任何一个key。
     * 要求】
     * Insert、 delete和 getRandom方法的时间复杂度都是0(1)
     *
     * 这个不难
     * */
    public static class Pool{

    }

    /**
     * 布隆过滤器
     *
     * 有添加有查询无删除的集合
     * 占用空间少,支持海量数据
     * 并且有可能会失误,但是失误有限制的
     * 如查询一条数据是否在集合内,
     * 失误只可能是将不在集合内的误报成在集合中(概率很低)
     * 但不会将在集合中的误报成不在
     *
     * 利用位图
     * 以URL为例一条URL的N的字符,每个字符都通过hash函数计算出
     * 应该将位图中的哪一位置一.
     * 查询的时候同样,如果发现每一位都置一的那就是在集合中了
     *
     * 已知:
     * n = 样本量  p = 失误率
     * 求所占空间m需要的哈希个数k和实际的失误率P
     * m = -(n*lnp)/((ln2)^2) (Byte)
     * m/=8得到位图所占空间大小
     * k = ceil(ln2 * m/n)
     * P = (1-exp(-(n*k/m)))^k  //实际失误率 p是理论失误率
     *
     * */
    /**
     * 哈希一致性原理的用处
     * 问题背景:
     * 以前我们存储数据的时候都是尽量往一个机器上存储
     * 但是数据一旦多起来,对机器的性能要求就会比较高
     * ,这个时候就会增加机器,假设以前有三台机器,每条数
     * 数算出来的哈希%3得到数据存放的机器编号,现在要加
     * 一台机器,这个时候我们就要重新组织所有的机器,即
     * 将以前三台的机器中的数据都拿出来,计算哈希再%4
     * 来重新组织分配数据,3台机器还好,但是假如100台呢
     * 这种经典方法对机器的增添删除不友好
     * 现在有一种新的方法如下:
     * 假设我们只有三台机器,但是可以预知到未来很长一段时间
     * 机器最多会增长到256台,那么我们就可以将机器的MAC地址
     * 或者IP地址,计算哈希,使这三台机器均匀的分布在0-255的
     * 范围上,然后让机器0管理计算出机器位置在0-256/3的所有数据
     * 机器1处理256/3-256/3*2的数据...(可以看做一个环)
     * 假如这个时候假如一个机器4,那么理想情况下机器4可以插入到
     * 机器2-机器0 之间然后只需要将机器2上的数据重新整理一下
     * 机器0机器1的数据都不用动,提高了效率.
     * 但是现在问题就是如何才能让机器的分布尽量均匀
     *
     * 解决办法:
     * 虚拟节点技术
     * 我们知道哈希技术可以实现大量数据时的均匀分布
     * 那么我们可以让机器0-2,这三个机器离散成3000个虚拟节点
     * 这样就能保证每个机器管理的数据时均匀分布的
     * 注意参与分配工作区域的时候是每台机器内部的虚拟节点去抢
     * 而不是机器去抢,那么在添加机器3的时候同样分化成1000个虚拟节点
     * 然后每个节点同周围的节点重新组织数据长度是环的长度/4
     *
     * 另外还能做到负载均衡,如果机器0性能比较强,那么机器0则
     * 可以虚拟出2000个节点,机器1比较弱那么久虚拟成100个节点
     *
     *
     *
     *
     * */
    public static void main(String[] args) {
        int[] arr = new int[10];
        int index = 178;
        int numIndex = index/32;
        int bitIndex = index%32;
        int state = (arr[numIndex] >>> bitIndex)&1;//check
        arr[numIndex] = arr[numIndex] | (1<<numIndex);//set
        arr[numIndex] = arr[numIndex] & (~(1<<numIndex));//reset

    }




}
